<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // NO.1 多数元素

      // 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
      // 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
      // 示例 1：
      // 输入：[3,2,3]
      // 输出：3

      // 示例 2：
      // 输入：[2,2,1,1,1,2,2]
      // 输出：2

      /**
       * @param {number[]} nums
       * @return {number}
       */
      // 思路1：声明一个初始值0和一个数组第一项值假定作为多数元素，往后和循环的每一项比较 如果相同初始值+1，不同就减少1，
      // 当初始值再次等于0的时候 说明当前出现nums[i]的次数大于初始值 nums[0]，则改变 count为当前 nums[i]作为多数元素，循环结束时，可以得到这个 count就是多数元素
      // var majorityElement = function (nums) {
      //   let count = nums[0]
      //   let res = 0
      //   for (let i = 0; i < nums.length; i++) {
      //     if (count == nums[i]) {
      //       res++
      //     } else {
      //       res--
      //     }
      //     if (res == 0) {
      //       count = nums[i]
      //       res++
      //     }
      //   }
      //   return count
      // }

      // 思路2:根据数组的元素进行排序方法 从小到大 进行排序 根据中间的那一个元素可以得到 大于 ⌊ n/2 ⌋ 的元素为多数元素
      // var majorityElement = function (nums) {
      //   nums.sort(function (a, b) {
      //     return a - b
      //   })
      //   return nums[parseInt(nums.length / 2)]
      // }
      // console.log(majorityElement([1, 2, 3, 3, 4, 4, 4, 4]), '结果')

      // NO.2 两数之和
      // 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
      // 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
      // 你可以按任意顺序返回答案。
      //示例 1：
      // 输入：nums = [2,7,11,15], target = 9
      // 输出：[0,1]
      // 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

      // 示例 2：
      // 输入：nums = [3,2,4], target = 6
      // 输出：[1,2]

      // 示例 3：
      // 输入：nums = [3,3], target = 6
      // 输出：[0,1]
      // 思路一：暴力枚举 2个for循环一次遍历，外层循环一次内层从第二个元素开始往后循环，一次比较值是否等于target.
      // var twoSum = function (nums, target) {
      //   let arr = ''
      //   for (let i = 0; i < nums.length; i++) {
      //     for (let j = i + 1; j < nums.length; j++) {
      //       if (nums[i] + nums[j] == target && i !== j) {
      //         arr = `${i},${j}`
      //       }
      //     }
      //   }
      //   return arr.split(',')
      // }
      // 方法2.哈希表：
      // 思路：方法一第一层循环是必须的，关键是优化第二次循环，也就是寻找targrt-x的过程，这里关键采用空间换时间，也就是采用哈希表进行优化，
      // 让查找的过程变为O(1)。首先还是遍历nums数组，然后在哈希表中寻找target-x，如果不存在就把当前元素x和下标存入哈希表，如果存在就返回target-x和当前元素的下标
      // var twoSum = function (nums, target) {
      //   const map = new Map()
      //   for (let i = 0; i < nums.length; i++) {
      //     //第一层循环
      //     const complement = target - nums[i]
      //     // 利用差值来找第二个数
      //     if (map.has(complement)) {
      //       //判断complement是否在map中
      //       return [map.get(complement), i] //存在的话返回两个数的下标
      //     } else {
      //       map.set(nums[i], i) //不存在map中就将当前元素和下标存入map
      //     }
      //   }
      //   return []
      // }

      // NO.3 用两个栈实现队列
      // 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

      // 示例 1：
      // 输入：
      // ["CQueue","appendTail","deleteHead","deleteHead"]
      // [[],[3],[],[]]
      // 输出：[null,null,3,-1]

      // 示例 2：
      // 输入：
      // ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
      // [[],[],[5],[2],[],[]]
      // 输出：[null,-1,null,null,5,2]

      // 思路：首先我们知道，队列是先入先出，栈是后入先出，所以知道了这两个东西的特性，我们很容易就能根据题意使用两个栈来模拟队列。
      // 首先，两个栈分工不同，一个为入队栈，一个为出队栈，各自负责入队和出队。
      // 入队操作，直接压入入队栈即可，出队操作需要优先检查出队栈是否有数据，若无，需要从入队栈倒入后再操作

      // var CQueue = function () {
      //   // 栈是后入先出！！！！
      //   this.inStrack = [] //入队栈
      //   this.outStrack = [] //出队栈
      // }
      // /**
      //  * @param {number} value
      //  * @return {void}
      //  */
      // CQueue.prototype.appendTail = function (value) {
      //   this.inStrack.push(value)
      // }
      // /**
      //  * @return {number}
      //  */
      // CQueue.prototype.deleteHead = function () {
      //   if (this.outStrack.length) {
      //     return this.outStrack.pop()
      //   } else {
      //     while (this.inStrack.length) {
      //       this.outStrack.push(this.inStrack.pop())
      //     }
      //     if (!this.outStrack.length) {
      //       return -1
      //     } else {
      //       return this.outStrack.pop()
      //     }
      //   }
      // }
      // var CQueue = function () {
      //   this.queueList = []
      //   return null
      // }

      // /**
      //  * @param {number} value
      //  * @return {void}
      //  */
      // CQueue.prototype.appendTail = function (value) {
      //   this.queueList.push(value)
      //   return null
      // }

      // /**
      //  * @return {number}
      //  */
      // CQueue.prototype.deleteHead = function () {
      //   return this.queueList.shift() || -1
      // }

      // NO.3 包含min函数的栈
      // 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
      // 示例:
      // MinStack minStack = new MinStack();
      // minStack.push(-2);
      // minStack.push(0);
      // minStack.push(-3);
      // minStack.min();   --> 返回 -3.
      // minStack.pop();
      // minStack.top();      --> 返回 0.
      // minStack.min();   --> 返回 -2.
      // var MinStack = function () {
      //   this.Stack = []
      //   this.minStack = []
      // }
      // MinStack.prototype.push = function (x) {
      //   this.Stack.push(x)
      //   this.minStack.push(Math.min(this.minStack[this.minStack.length - 1], x))
      // }
      // MinStack.prototype.pop = function () {
      //   this.Stack.pop()
      //   this.minStack.pop()
      // }
      // /**
      //  * @return {number}
      //  */
      // MinStack.prototype.top = function () {
      //   return this.Stack[this.Stack.length - 1]
      // }
      // /**
      //  * @return {number}
      //  */
      // MinStack.prototype.min = function () {
      //   return this.minStack[this.minStack.length - 1]
      // }

      // NO.4 反转链表
      // 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

      // 示例:
      // 输入: 1->2->3->4->5->NULL
      // 输出: 5->4->3->2->1->NULL
      /**
       * Definition for singly-linked list.
       * function ListNode(val) {
       *     this.val = val;
       *     this.next = null;
       * }
       */
      /**
       * @param {ListNode} head
       * @return {ListNode}
       */
      // var reverseList = function (head) {
      //   let list = new ListNode('0')
      //   let result = []
      //   let he = list
      //   while (head) {
      //     let val = head == null ? 0 : head.val
      //     result.push(val)
      //     console.log(result, 'result')
      //     if (head) {
      //       head = head.next
      //     }
      //   }
      //   let re = result.reverse()
      //   while (re.length > 0 && list) {
      //     let a = re[0]
      //     list.next = new ListNode(a)
      //     if (list) {
      //       list = list.next
      //     }
      //     re.splice(0, 1)
      //   }
      //   return he.next
      // }

      // 思路：1. 利用3个变量在循环过程中记录最后3种信息
      // cur游标，一直往后循环，最后会为null
      // prev记录前一个节点
      // oldNext，变更方向时，需要先用oldNext记住改变前的next节点，否则无法向后循环
      // let head = {
      //   val: 2,
      //   next: {
      //     val: 4,
      //     next: {
      //       val: 3,
      //       next: null,
      //     },
      //   },
      // }
      // var reverseList = function (head) {
      //   var prev = null,
      //     cur = head,
      //     temp
      //   while (cur) {
      //     temp = cur.next //修改前先记住下一个节点 (临时存储，然后易值)
      //     cur.next = prev //改别指向，第一个节点prev是null,
      //     prev = cur //记录前一个节点，供下次循环使用
      //     cur = temp // cur通过temp指向下一节点
      //   }
      //   return prev //cur会多循环直到null
      // }

      // NO.5  左旋转字符串
      // 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。
      // 比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

      // 示例 1：
      // 输入: s = "abcdefg", k = 2
      // 输出: "cdefgab"

      // 示例 2：
      // 输入: s = "lrloseumgh", k = 6
      // 输出: "umghlrlose"
      /**
       * @param {string} s
       * @param {number} n
       * @return {string}
       */
      // var reverseLeftWords = function (s, n) {
      //   return s.slice(n, s.length) + s.slice(0, n)
      // }

      // NO.6  数组中重复的数字
      // 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
      // 请找出数组中任意一个重复的数字。
      // 示例 1：
      // 输入：
      // [2, 3, 1, 0, 2, 5, 3]
      // 输出：2 或 3
      // var findRepeatNumber = function (nums) {
      //   let map = new Map()
      //   for (let i of nums) {
      //     if (map.has(i)) return i
      //     map.set(i, 1)
      //   }
      //   return null
      // }

      // NO.7  在排序数组中查找数字
      //  统计一个数字在排序数组中出现的次数。
      // 示例 1:
      // 输入: nums = [5,7,7,8,8,10], target = 8
      // 输出: 2

      // 示例 2:
      // 输入: nums = [5,7,7,8,8,10], target = 6
      // 输出: 0
      // var search = function (nums, target) {
      //   let map = new Map()
      //   for (let i of nums) {
      //     if (map.has(i)) {
      //       map.set(i, map.get(i) + 1)
      //     } else {
      //       map.set(i, 1)
      //     }
      //   }
      //   return map.get(target) || 0
      // }

      // 二分查找
      // const search = (nums, target) => {
      //   // 定义上下限、找到的标志flag
      //   let [low, high, flag] = [0, nums.length - 1, null]

      //   while (low <= high) {
      //     const mid = (low + high) >> 1
      //     const midNum = nums[mid]
      //     if (midNum > target) {
      //       high = mid - 1
      //     } else if (midNum < target) {
      //       low = mid + 1
      //     } else {
      //       // 如果找到了，将mid赋值给flag，存的是索引
      //       flag = mid
      //       // 找到一个，直接退出循环
      //       break
      //     }
      //   }
      //   // while结束后，判断是否找到，没找到直接返回0
      //   if (flag === null) return 0

      //   // 从flag开始，向两边扩散
      //   low = high = flag
      //   while (nums[low - 1] === target) low--
      //   while (nums[high + 1] === target) high++

      //   // 返回计数
      //   return high - low + 1
      // }

      // console.log(search([5, 7, 7, 8, 8, 10], 6))

      // NO.8  0～n-1中缺失的数字
      //  一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
      //  在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
      // 示例 1:
      // 输入: [0,1,3]
      // 输出: 2

      // 示例 2:
      // 输入: [0,1,2,3,4,5,6,7,9]
      // 输出: 8
      // var missingNumber = function (nums) {
      //   nums.push(0)
      //   let temp = ''
      //   for (let i = 0; i < nums.length; i++) {
      //     if (nums[i] != i) {
      //       temp = i
      //     }
      //   }
      //   return temp
      // }
      // ad地址：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
      // 原文地址：https://xxoo521.com/2020-03-14-missing-number/
      /**
       * @param {number[]} nums
       * @return {number}
       */
      // var missingNumber = function (nums) {
      //   let left = 0,
      //     right = nums.length - 1
      //   while (left <= right) {
      //     let mid = Math.floor((left + right) / 2)
      //     if (mid === nums[mid]) {
      //       left = mid + 1
      //     } else if (mid < nums[mid]) {
      //       right = mid - 1
      //     }
      //   }
      //   return left
      // }

      // console.log(missingNumber([0, 1, 2, 3, 4, 5, 6, 7, 9]))

      // NO.9  第一个只出现一次的字符
      // 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
      // 示例 1:
      // 输入：s = "abaccdeff"
      // 输出：'b'

      // 示例 2:
      // 输入：s = ""
      // 输出：' '

      // var firstUniqChar = function (s) {
      //   if (s.length === 0) return ' '
      //   let map = new Map()
      //   for (let i of s) {
      //     if (!map.has(i)) {
      //       map.set(i, 1)
      //     } else {
      //       map.set(i, map.get(i) + 1)
      //     }
      //   }
      //   for (let i = 0; i < s.length; i++) {
      //     if (map.get(s[i]) === 1) {
      //       return s[i]
      //       break
      //     }
      //   }
      //   return ' '
      //   // console.log('map', map.keys())
      // }

      // console.log(firstUniqChar('abaccdeff'))

      // NO.10  从上到下打印二叉树
      // 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
      // 例如:
      // 给定二叉树: [3,9,20,null,null,15,7],
      //     3
      //    / \
      //   9  20
      //     /  \
      //    15   7
      // 返回：
      // [3,9,20,15,7]
      /**
       * Definition for a binary tree node.
       * function TreeNode(val) {
       *     this.val = val;
       *     this.left = this.right = null;
       * }
       */
      /**
       * @param {TreeNode} root
       * @return {number[]}
       */
      // let tree = {
      //   val: 3,
      //   left: {
      //     val: 9,
      //     left: null,
      //     right: null,
      //   },
      //   right: {
      //     val: 20,
      //     left: {
      //       val: 15,
      //       left: null,
      //       right: null,
      //     },
      //     right: {
      //       val: 7,
      //       left: null,
      //       right: null,
      //     },
      //   },
      // }
      // var levelOrder = function (root) {
      //   if (!tree) return []
      //   let arr = [root]
      //   let res = []
      //   while (arr.length > 0) {
      //     debugger
      //     let data = arr.shift()
      //     res.push(data.val)
      //     if (data.left) {
      //       arr.push(data.left)
      //     }
      //     if (data.right) {
      //       arr.push(data.right)
      //     }
      //   }
      //   return res
      // }
      // levelOrder(tree)

      // NO.11  从上到下打印二叉树 II
      // 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
      // 例如:
      // 给定二叉树: [3,9,20,null,null,15,7],
      //     3
      //    / \
      //   9  20
      //     /  \
      //    15   7
      // 返回其层次遍历结果：

      // [
      //   [3],
      //   [9,20],
      //   [15,7]
      // ]
      /**
       * @param {TreeNode} root
       * @return {number[][]}
       */
      //  请实现一个函数按照之字形顺序打印二叉树，
      //  即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
      // let tree = {
      //   val: 4,
      //   left: {
      //     val: 2,
      //     left: {
      //       val: 1,
      //       left: null,
      //       right: null,
      //     },
      //     right: {
      //       val: 3,
      //       left: null,
      //       right: null,
      //     },
      //   },
      //   right: {
      //     val: 7,
      //     left: {
      //       val: 6,
      //       left: null,
      //       right: null,
      //     },
      //     right: {
      //       val: 9,
      //       left: null,
      //       right: null,
      //     },
      //   },
      // }
      // var levelOrder = function (root) {
      //   if (!root) return []
      //   let rootList = [root]
      //   let res = []
      //   let level = 0
      //   while (rootList.length > 0) {
      //     res[level] = []
      //     let num = rootList.length
      //     while (num > 0) {
      //       let data = rootList.shift()
      //       if (level % 2 === 0) {
      //         res[level].push(data.val)
      //       } else {
      //         res[level].unshift(data.val)
      //       }

      //       if (data.left) {
      //         rootList.push(data.left)
      //       }
      //       if (data.right) {
      //         rootList.push(data.right)
      //       }

      //       num--
      //     }
      //     level++
      //   }
      //   return res
      // }
      // levelOrder(tree)

      // NO.12  二叉树的镜像
      // 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
      // 例如输入：

      //      4
      //    /   \
      //   2     7
      //  / \   / \
      // 1   3 6   9
      // 镜像输出：

      //      4
      //    /   \
      //   7     2
      //  / \   / \
      // 9   6 3   1

      // var mirrorTree = function (root) {
      //   if (!root) return null
      //   const left = mirrorTree(root.left)

      //   const right = mirrorTree(root.right)

      //   root.left = right
      //   root.right = left
      //   return root
      // }
      // mirrorTree(tree)

      // NO.13  对称的二叉树
      // 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
      // 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

      //     1
      //    / \
      //   2   2
      //  / \ / \
      // 3  4 4  3
      // 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

      //     1
      //    / \
      //   2   2
      //    \   \
      //    3    3

      /**
       * @param {TreeNode} root
       * @return {boolean}
       */
      // let tree = {
      //   val: 1,
      //   left: {
      //     val: 2,
      //     left: {
      //       val: 3,
      //       left: null,
      //       right: null,
      //     },
      //     right: {
      //       val: 4,
      //       left: null,
      //       right: null,
      //     },
      //   },
      //   right: {
      //     val: 2,
      //     left: {
      //       val: 4,
      //       left: null,
      //       right: null,
      //     },
      //     right: {
      //       val: 3,
      //       left: null,
      //       right: null,
      //     },
      //   },
      // }
      // var isSymmetric = function (root) {
      //   if (!root) return true

      //   return dis(root.left, root.right)
      //   function dis(left, right) {
      //     if (left == null && right == null) {
      //       return true
      //     } else if (left == null || right == null || left.val !== right.val) {
      //       return false
      //     } else {
      //       return dis(left.left, right.right) && dis(left.right, right.left)
      //     }
      //   }
      // }
      // console.log(isSymmetric(tree))

      // NO.14  斐波那契数列
      // 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

      // F(0) = 0,   F(1) = 1
      // F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

      // 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

      // 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
      //
      // 示例 1：
      // 输入：n = 2
      // 输出：1

      // 示例 2：
      // 输入：n = 5
      // 输出：5
      var fib = function (n) {
        if (n === 0) {
            return 0
          }
          if (n === 1) {
            return 1  
          }        
        function F(n) {
          return F(n-1)+F(n-2)
        }
        F2=F1+F0
        F3=F2+F1
        F4=F3+F2
        F5=F4+F3
        F6=F5+F4




      }
    </script>
  </body>
</html>
